tarjan-graph

What is tarjan-graph?

The tarjan-graph npm package is a JavaScript library that implements Tarjan's algorithm to find strongly connected components in a directed graph. This is useful in various applications such as analyzing networks, optimizing paths, and detecting cycles in complex systems.

What are tarjan-graph's main functionalities?

Finding Strongly Connected Components

This feature allows you to find and list all strongly connected components in a directed graph. A strongly connected component (SCC) is a subset of the graph where every vertex is reachable from every other vertex in the same subset.

const TarjanGraph = require('tarjan-graph');
const graph = new TarjanGraph();
graph.add('A', ['B']);
graph.add('B', ['C']);
graph.add('C', ['A']);
const scc = graph.getStronglyConnectedComponents();
console.log(scc);

Cycle Detection

This feature checks if the directed graph contains any cycles. A cycle exists when there is a path from a node back to itself through directed edges.

const TarjanGraph = require('tarjan-graph');
const graph = new TarjanGraph();
graph.add('X', ['Y']);
graph.add('Y', ['Z']);
graph.add('Z', ['X']);
const hasCycle = graph.hasCycle();
console.log(hasCycle);

Other packages similar to tarjan-graph

strongly-connected-components

This package also finds strongly connected components in a directed graph. It is similar to tarjan-graph but might differ in implementation details and API design, offering users alternatives based on their specific needs or preferences.

graphology

Graphology is a comprehensive graph analysis library. While it includes functionality for finding strongly connected components, it also provides a wide range of other graph-related algorithms and utilities, making it more versatile than tarjan-graph if broader graph analysis capabilities are needed.

README

tarjan-graph

This is a simple directed graph lib, mostly just for checking if a directed graph contains a cycle. It uses Tarjan's algorithm for checking if the graph contains a cycle.

This library also has some very basic Graphviz support for visualizing graphs using the DOT language.

Installation

Note: as of v1.0.0 this library requires node >= v8.0.0. Use v0.3.0 for node < v8.0.0.

npm install tarjan-graph

Usage

All examples use the following graph:

node -e "
const Graph = require('tarjan-graph');

const graph = new Graph()
  .add('a', ['b', 'c'])
  .add('b', ['d', 'e'])
  .add('c', ['b'])
  .add('d', ['e'])
  .add('e', ['c'])
  .add('f', ['c', 'a', 'g'])
  .add('g', ['h', 'i'])
  .add('h', ['j'])
  .add('i', ['j'])
  .add('j', ['f', 'k'])
  .add('k', ['k']);

console.log(graph.toDot());
" | dot -o docs/example-graph.png -Tpng

Doing stuff with cycles:

console.log(graph.hasCycle()); 
//true
console.log(graph.getCycles());
// [ 
//   [ { name: 'b', successors: [...] }, { name: 'e', ... }, ... ], 
//   ... 
// ]

//use addAndVerify() instead of add() to throw an error when adding
//an edge would create a cycle

Doing stuff with SCCs:

//same as graph.getCycles() except includes single vertices
console.log(graph.getStronglyConnectedComponents());

Searching:

//depth-first search (pre-order)
graph.dfs('g', (v) => {
  console.log(v.name + ': ' + v.successors.map(w => w.name).join(', '));
});
/*
g: i, h
h: j
j: k, f
f: g, a, c
c: b
b: e, d
d: e
e: c
a: c, b
k: k
i: j
*/

//retrieve descendants
console.log(graph.getDescendants('a'));
//[ 'b', 'd', 'e', 'c' ]

And of course, dat dot:

console.log(graph.toDot());
/*
digraph {
  subgraph cluster0 {
    color=red;
    d; c; e; b;
  }
  subgraph cluster1 {
    color=red;
    k;
  }
  subgraph cluster2 {
    color=red;
    h; f; j; i; g;
  }
  b -> e
  b -> d
  c -> b
  a -> c
  a -> b
  d -> e
  e -> c
  g -> i
  g -> h
  f -> g
  f -> a
  f -> c
  h -> j
  i -> j
  j -> k
  j -> f
  k -> k
}
*/